package com.stackandqueue;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution05 {
    public String removeDuplicates(String s) {
        LinkedList<Character> deque = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (deque.isEmpty() || c != deque.getLast()) {
                deque.add(c);
            } else deque.removeLast();
        }
        StringBuilder res = new StringBuilder();
        while (!deque.isEmpty()) {
            res.append(deque.removeFirst());
        }
        return res.toString();
    }
}
